package com.fzn3.day01;

/**
 * @program: DataStructure
 * @author: fzn
 * 描述: 二分查找
 * @create: 2023/3/3 15:38
 **/
public class BinarySearch {

    /**
     * 二分查找基础版
     *
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchBase(int[] arr, int target) {
        // 设置两个指针
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            // 中间数 如果相加超出范围就会溢出 会出现问题
            // int m = (i + j) / 2;
            // 无符号右移1位 相当于/2 是因为java默认把最高位为符号位所以要使用无符号右移
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                // 左边
                j = m - 1;
            } else if (arr[m] < target) {
                // 右边
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 二分查找改动版
     *
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchAlternative(int[] arr, int target) {
        // 设置两个指针  j指向的不是查找目标所以要用 i < j
        int i = 0, j = arr.length;
        while (i < j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                // 左边
                j = m;
            } else if (arr[m] < target) {
                // 右边
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 二分查找 平衡版
     * 减少循环的比较次数
     *
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchBalance(int[] arr, int target) {
        int i = 0, j = arr.length;
        while (1 < j - i) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                // 左边
                j = m;
            } else {
                i = m;
            }
        }
        return arr[i] == target ? i : -1;
    }

    /**
     * 二分查找Leftmost 查询重复最左边的元素
     *
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchLeftmost1(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                // 左边
                j = m - 1;
            } else if (arr[m] < target) {
                // 右边
                i = m + 1;
            } else {
                // 记录候选位置
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    /**
     * 二分查找Rightmost 查询重复最右边的元素
     *
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchRightmost1(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                // 左边
                j = m - 1;
            } else if (arr[m] < target) {
                // 右边
                i = m + 1;
            } else {
                // 记录候选位置
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }

    /**
     * 二分查找Leftmost 查询重复最左边的元素
     *
     * @param arr
     * @param target
     * @return  返回大于等于目标最靠左的位置
     */
    public static int binarySearchLeftmost2(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= arr[m]) {
                j = m - 1;
            } else{
                i = m + 1;
            }
        }
        return i;
    }

    /**
     * 二分查找Rightmost 查询重复最右边的元素
     *
     * @param arr
     * @param target
     * @return 返回小于等于目标最靠右的位置
     */
    public static int binarySearchRightmost2(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m - 1;
            } else{
                i = m + 1;
            }
        }
        return i-1;
    }
}
